// 优先级队列
class PriorityQueue {
    constructor(compare) {
        this.elements = [];//使用数组存储元素
        this.compare = compare || ((a, b) => a - b);
    }
    //enqueue方法添加元素后会对数组进行排序
    enqueue(element) {
        this.elements.push(element);
        this.elements.sort(this.compare);
    }
    //dequeue方法取出第一个元素(优先级最高的)
    dequeue() {
        return this.elements.shift();
    }
    //isEmpty检查队列是否为空
    isEmpty() {
        return this.elements.length === 0;
    }
}
// 全局开关变量:默认不开启
let enableOptimization = false;


// 标记A1约束区域边界
function markConstraintArea(grid, start, end) {
    // 清除旧标记
    document.querySelectorAll('.constraint-marker').forEach(el => el.remove());

    // 计算矩形区域边界
    const minX = Math.min(start.x, end.x);
    const maxX = Math.max(start.x, end.x);
    const minY = Math.min(start.y, end.y);
    const maxY = Math.max(start.y, end.y);

    // 创建边界标记
    for (let x = minX; x <= maxX; x++) {
        for (let y = minY; y <= maxY; y++) {
            if (x === minX || x === maxX || y === minY || y === maxY) {
                //标记边界
                const cell = grid.cells[x][y];
                if (!cell.isWall) {
                    const marker = document.createElement('div');
                    marker.className = 'constraint-marker';
                    marker.textContent = '■'; // 使用实心方块符号
                    // 不同边界使用不同符号（可选）
                    if (x === minX) marker.textContent = '▲';
                    if (x === maxX) marker.textContent = '▼';
                    if (y === minY) marker.textContent = '◀';
                    if (y === maxY) marker.textContent = '▶';
                    cell.element.appendChild(marker);
                }
            }
        }
    }
    // 分析并标记边界障碍连通块,注释后仅显示A1区域
    analyzeBorderObstacles(grid, start, end);
}

// 标记A2约束区域边界
function markA2Area(grid, extremes, start = grid.start, end = grid.end) {
    // 参数验证
    if (!grid || !grid.cells || !start || !end) {
        console.error("markA2Area: 缺少必要参数");
        return;
    }
    // 清除旧的A2标记
    document.querySelectorAll('.a2-marker').forEach(el => el.remove());

    // 计算A1区域边界（作为默认值）
    const a1MinX = Math.min(start.x, end.x);
    const a1MaxX = Math.max(start.x, end.x);
    const a1MinY = Math.min(start.y, end.y);
    const a1MaxY = Math.max(start.y, end.y);

    // 计算A2区域边界
    let minX = a1MinX;
    let maxX = a1MaxX;
    let minY = a1MinY;
    let maxY = a1MaxY;

    // 如果有有效极值点，则扩展A2区域
    const validPoints = Object.values(extremes || {}).filter(pos => 
        pos && pos[0] !== undefined && pos[1] !== undefined
    );
    if (validPoints.length > 0) {
        minX = Math.max(Math.min(...validPoints.map(p => p[0])) - 1, 0);
        maxX = Math.min(Math.max(...validPoints.map(p => p[0])) + 1, grid.rows - 1);
        minY = Math.max(Math.min(...validPoints.map(p => p[1])) - 1, 0);
        maxY = Math.min(Math.max(...validPoints.map(p => p[1])) + 1, grid.cols - 1);
        
        // 确保A2区域至少包含A1区域
        minX = Math.min(minX, a1MinX);
        maxX = Math.max(maxX, a1MaxX);
        minY = Math.min(minY, a1MinY);
        maxY = Math.max(maxY, a1MaxY);
    }

    // 标记区域边界
    for (let x = minX; x <= maxX; x++) {
        for (let y = minY; y <= maxY; y++) {
            if (x === minX || x === maxX || y === minY || y === maxY) {
                const cell = grid.cells[x][y];
                if (!cell.isWall) {
                    const marker = document.createElement('div');
                    marker.className = 'a2-marker';
                    
                    // 使用不同符号标记不同边界
                    if (x === minX) marker.textContent = '▼';
                    if (x === maxX) marker.textContent = '▲';
                    if (y === minY) marker.textContent = '▶';
                    if (y === maxY) marker.textContent = '◀';
                    
                    cell.element.appendChild(marker);
                }
            }
        }
    }
}


// 寻路算法
async function findPath(grid, start, end, algorithm) {
    // 先标记约束区域
    markConstraintArea(grid, start, end);
    //获取地图以及选择算法
    const cells = grid.getMapData();
    // 初始化开放列表（区分A*/Dijkstra）
    const openSet = new PriorityQueue((a, b) => 
        algorithm === 'astar' ? (a.f - b.f) : (a.g - b.g));
    // 获取A2区域边界（如果优化开启）
    let a2Bounds = null;
    if (enableOptimization) {
        a2Bounds = getA2Bounds(grid);
    }
    // 初始化节点状态
    cells.forEach(row => row.forEach(cell => {
        cell.g = Infinity;
         // 启发式函数设置:Dijkstra是A*在启发式函数中预估代价h=0时的特例
        cell.h = algorithm === 'astar' ? 
            Math.abs(cell.x - end.x) + Math.abs(cell.y - end.y) : 0;
        cell.f = cell.g + cell.h;
        cell.parent = null;
        cell.element.classList.remove('visited', 'current', 'path');
    }));

    cells[start.x][start.y].g = 0;
    openSet.enqueue(cells[start.x][start.y]);
    // 主循环（两者通用）
    while (!openSet.isEmpty()) {
        const current = openSet.dequeue();
        
        // 高亮当前节点
        current.element.classList.add('current');
        await new Promise(r => setTimeout(r, 30));

        // 到达终点
        if (current.x === end.x && current.y === end.y) {
            // markPath(current);
            // return true;
            return markPath(current);
        }

        // 标记为已访问
        current.element.classList.remove('current');
        if (!(current.x === start.x && current.y === start.y)) {
            current.element.classList.add('visited');
        }

        // 获取相邻节点
        const neighbors = [];
        const directions = [[-1,0], [1,0], [0,-1], [0,1]];
        directions.forEach(([dx, dy]) => {
            const x = current.x + dx;
            const y = current.y + dy;
            // 边界检查
            if (x >= 0 && x < grid.rows && y >= 0 && y < grid.cols) {
                // 如果开启优化且定义了A2边界，检查是否在A2区域内
                if (enableOptimization && a2Bounds) {
                    if (x < a2Bounds.minX || x > a2Bounds.maxX || 
                        y < a2Bounds.minY || y > a2Bounds.maxY) {
                        return; // 跳过不在A2区域内的节点
                    }
                }
                const neighbor = cells[x][y];
                //将空白邻点加入邻居节点集
                if (!neighbor.isWall) neighbors.push(neighbor);
            }
        });
        //将邻居节点加入openSet
        for (const neighbor of neighbors) {
            const tentativeG = current.g + 1;
            if (tentativeG < neighbor.g) {
                neighbor.g = tentativeG;
                neighbor.f = neighbor.g + neighbor.h;
                neighbor.parent = current;
                openSet.enqueue(neighbor);
            }
        }
    }
    return false;
}
// 获取A2区域边界的函数
function getA2Bounds(grid) {
    const markers = document.querySelectorAll('.a2-marker');
    if (markers.length === 0) return null;
    
    let minX = Infinity, maxX = -Infinity;
    let minY = Infinity, maxY = -Infinity;
    
    markers.forEach(marker => {
        const cell = marker.closest('.cell');
        const x = parseInt(cell.dataset.x);
        const y = parseInt(cell.dataset.y);
        
        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x);
        minY = Math.min(minY, y);
        maxY = Math.max(maxY, y);
    });  
    return { minX, maxX, minY, maxY };
}
// 标记路径
function markPath(node) {
    var lens=0;
    let current = node;
    while (current.parent) {
        current.element.classList.add('path');
        current = current.parent;
        lens++;
    }
    console.log(lens);
    return lens;
}


// 清除约束区域标记(目前没有使用这个函数)
// function clearConstraintMarkers() {
//     document.querySelectorAll('.constraint-marker').forEach(el => el.remove());
// }


// 分析边界障碍块所属联通体
function analyzeBorderObstacles(grid, start, end) {
    const minX = Math.min(start.x, end.x);
    const maxX = Math.max(start.x, end.x);
    const minY = Math.min(start.y, end.y);
    const maxY = Math.max(start.y, end.y);
    //联通体以当前障碍块的八向为基础
    const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    const visited = new Set();
    let borderComponents = [];

    // A1区域内部不分析连通性
    const isInsideA1 = (x, y) => 
        x > minX && x < maxX && 
        y > minY && y < maxY;

    // 步骤1：收集边界障碍块
    const borderObstacles = [];
    const isOnBorder = (x, y) => 
        (x === minX || x === maxX || y === minY || y === maxY);
    
    // 仅处理边界上的障碍块
    for (let x = minX; x <= maxX; x++) {
        for (let y = minY; y <= maxY; y++) {
            if (isOnBorder(x, y) && grid.cells[x][y].isWall) {
                borderObstacles.push([x, y]);
            }
        }
    }

    // 步骤2：BFS遍历联通体（仅向外探索）
    borderObstacles.forEach(([startX, startY]) => {
        if (visited.has(`${startX},${startY}`)) return;
        
        const queue = [[startX, startY]];
        const component = [];
        visited.add(`${startX},${startY}`);
        
        while (queue.length) {
            const [x, y] = queue.shift();
            component.push([x, y]);
            
            directions.forEach(([dx, dy]) => {
                const nx = x + dx;
                const ny = y + dy;
                const key = `${nx},${ny}`;
                
                // 新增区域边界判断
                if (nx >= 0 && nx < grid.rows && 
                    ny >= 0 && ny < grid.cols &&
                    !visited.has(key) && 
                    grid.cells[nx][ny].isWall &&
                    !isInsideA1(nx, ny) // 仅处理外部区域
                ) {
                    visited.add(key);
                    queue.push([nx, ny]);
                }
            });
        }

        // 仅标记实际在区域外的连通块
        if (component.some(([x, y]) => !isInsideA1(x, y))) {
            borderComponents.push(component);
        }
    });

    // 步骤3：染色外部连通块
    borderComponents.forEach(component => {
        component.forEach(([x, y]) => {
            if (!isInsideA1(x, y)) { // 二次验证防止染色内部
                grid.cells[x][y].element.classList.add('external-connected-obstacle');
            }
        });
    });

    // 荧光轮廓连通块
    grid.borderComponents = borderComponents; // 存储分析结果
    initHoverEffect(); // 初始化悬停效果

    // 无论是否有连通体都标记极值点
    markGlobalExtremes(grid, start, end);

}

// 障碍体荧光轮廓
function initHoverEffect() {
    const cells = document.querySelectorAll('.cell');
    cells.forEach(cell => {
        cell.addEventListener('mouseenter', function(e) {
            const x = parseInt(this.dataset.x);
            const y = parseInt(this.dataset.y);
            if (!grid.cells[x][y].isWall) return;

            // 查找所属连通块
            const component = grid.borderComponents.find(comp => 
                comp.some(([cx, cy]) => cx === x && cy === y)
            );
            
            if (component) {
                // 计算轮廓边缘
                const outlineCells = getOutlineCells(component);
                outlineCells.forEach(([x, y]) => {
                    grid.cells[x][y].element.classList.add('glow-outline');
                });
            }
        });

        cell.addEventListener('mouseleave', function() {
            document.querySelectorAll('.glow-outline').forEach(el => {
                el.classList.remove('glow-outline');
            });
        });
    });
}

// 辅助函数：获取连通块轮廓边缘
function getOutlineCells(component) {
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    const outline = [];
    
    component.forEach(([x, y]) => {
        dirs.forEach(([dx, dy]) => {
            const nx = x + dx, ny = y + dy;
            // 判断是否为边缘
            if (!component.some(([cx, cy]) => cx === nx && cy === ny)) {
                outline.push([x, y]);
            }
        });
    });
    
    return [...new Set(outline.map(JSON.stringify))].map(JSON.parse);
}


// 标记全局极值点
function markGlobalExtremes(grid, start, end) {    
    let globalMinX = Infinity, globalMaxX = -Infinity;
    let globalMinY = Infinity, globalMaxY = -Infinity;
    let northCell = null, southCell = null, eastCell = null, westCell = null;
    // 遍历所有连通块寻找全局极值
    grid.borderComponents.forEach(component => {
        component.forEach(([x, y]) => {
            if (x < globalMinX) {
                globalMinX = x;
                northCell = [x, y];
            }
            if (x > globalMaxX) {
                globalMaxX = x;
                southCell = [x, y];
            }
            if (y < globalMinY) {
                globalMinY = y;
                westCell = [x, y];
            }
            if (y > globalMaxY) {
                globalMaxY = y;
                eastCell = [x, y];
            }
        });
    });

    // 清除旧的极值标记
    document.querySelectorAll('.global-extreme').forEach(el => {
        el.classList.remove('global-extreme', 'global-north', 'global-south', 'global-east', 'global-west');
    });

    // 标注特殊单元格
    const extremes = {
        '北': northCell,
        '南': southCell,
        '东': eastCell,
        '西': westCell
    };

    Object.entries(extremes).forEach(([dir, pos]) => {
        if (pos && pos[0] !== undefined && pos[1] !== undefined) {
            const [x, y] = pos;
            if (grid.cells[x] && grid.cells[x][y]) {
                const cell = grid.cells[x][y].element;
                cell.classList.add('global-extreme', `global-${dir}`);
                cell.dataset.globalDir = dir.toUpperCase();
            }
        }
    });

    // 总是调用markA2Area，传入start和end参数
    markA2Area(grid, {
        north: northCell,
        south: southCell,
        east: eastCell,
        west: westCell
    }, start, end);

    // 在markGlobalExtremes函数末尾调用A2区域生成
    if (northCell || southCell || eastCell || westCell) {
        markA2Area(grid, {
            north: northCell,
            south: southCell,
            east: eastCell,
            west: westCell
        });
    }
}

